This invention relates generally to raster graphics systems and more specifically to shading operations.
In a raster graphics system, smooth shading in colour is used for two main operations. The first is to fill directly in a geometrically defined area, and the second is to produce shading patterns and then paint a defined area with the smooth colour transition. There is a plurality of methods to define such shading mechanisms. In a raster image processor related to a printer, the Postscript Language Reference Manual defines seven types of shading and parameters via shading dictionaries. The Postscript Language Reference, Third Edition, Adobe Systems, Inc., published by Addison Wesley Publishing, is hereby incorporated by reference.
Shading provides a smooth transition between colours across an area to be painted, independent of the resolution of any particular output device and without specifying the number of steps in the colour transition. If the shading area is a simple geometric shape, the shading operations can be performed directly to paint the corresponding device pixels with the shading colour defined in a shading dictionary. However, in most cases, the required shading area is comprised of complicated geometric shapes, which warrant the definition of a shading pattern. In the Postscript Language reference manual, a Type 2 shading pattern dictionary defines this type of shading patterns. Such a pattern dictionary contains the entry of a shading dictionary. The shading dictionary specifies details of a particular gradient fill, including the type of shading to be used, the geometry of the area to be shaded, and the geometry of the gradient fill itself. In addition, the shading dictionary can contain a function dictionary—which is required for some types of shading and optional for others—that defines how the colour or colours vary across the area to be shaded. The seven types of shading can be grouped in to several categories including function-based shading, axial shading, radial shading, triangle meshes based shading and patch meshes based shading.
In a raster graphics system, the output device contains a predefined number of pixels arranged in a predefined layout, with an inherent device resolution. A particular device's coordinate system is named the device space. A device space origin can be anywhere on the output, depending on the usage of the device. When painting pixels on the device, each device pixel needs to be painted as defined by the painting instruction. Coordinates specified in a Postscript program refer to locations within a coordinate system, named user space, which always bears the same relationship to the current page, regardless of the output device.
The coordinate transformation from the user space to the device space is achieved using the current transformation matrix (CTM). This matrix contains information related to translation, rotation and scaling. It is represented as a six-element array given by:└a b c d tx ty┘The coordinate transformation from user space coordinate pair (x, y) to device coordinates (x′, y′) is given by the following equations.x′=ax+cy+txy′=bx+dy+ty
In the case of shading operations, each device pixel coordinate needs to be transferred to the coordinate system, named as the shading space, that is used to define the shading operation, in order to compute the colour values corresponding to that particular device pixel. This coordinate mapping involves computing a shading space coordinate pair (x″, y″) for a given (x′, y′) using the shading transformation matrix [a″ b″ c″ d″ t″x t″y], where its inverse matrix is given by,[ai″ bi″ ci″ di″ tix″ tiy″]=[a″ b″ c″ d″ t″x t″y ]−1and the correspondent mapping is defined as below:x″=ai″x′+ci″y′+tix″y″=bi″x′+di″y′+tiy″
In the case that a direct shading operation is invoked, such a shading space is the current user space. That is, for a pair (x″, y″), x″=x, y″=y and [a″ b″ c″ d″ t″x t″y]=CTM; However, in the case that a shading operation is used with a Type 2 pattern dictionary, the shading space is the pattern coordinate system (xp, yp) established at the time the shading pattern is instantiated with the PostScript operator makepattern. That means x″=xp, y″=yp and [a″ b″ c″ d″ t″x t″y]=[ap bp cp dp tpx tpy] (the compound pattern transformation matrix). Since each shaded device pixel needs to be mapped to the shading space to compute the corresponding pixel colour, shading operations are inherently computation intensive and thus inefficient.
Radial (Type 3) shading, as described by the Postscript Language reference manual, defines a colour blend that varies between two circles. They are commonly used to depict 3D spheres and cones. The blend circles are defined in terms of a subsidiary parametric variable, which varies linearly between 0.0 and 1.0. The parametric variable normally needs to be calculated first from a unique circle in shading coordinate space on that a particular point (x″, y″) resides. The resulting parametric variable is then used to compute the corresponding shading colour by use of a defined mathematical function in the Type 3 shading dictionary. When shading a device pixel, it is necessary to transform the device pixel to the shading coordinates, and identify the circle in which the mapped pixel resides. From the identified circle, the corresponding parametric variable can be found to determine the colour that should be painted on the current device pixel. Notice that the function dictionary is used in this type of shading operation. There are three types of function dictionaries supported in PostScript language level 3: the sampled function (Type 0), the exponential interpolation function (Type 2) and the stitching function (Type 3). These Function dictionaries are tightly associated with smooth shading operation, providing close control over the shape of the colour transitions across the geometry of the shading. The sampled function (Type 0) provides an approximation of any desired mathematical function based on a sequence of sampled values, using either linear or cubic interpolation as defined in the function dictionary. For a given function input, the surrounding nearest neighbor sample values of the input need to be located for performing any specified interpolation scheme.
Triangle meshes based (Types 4 and 5) shading, as described by the Postscript Language reference manual, defines the area to be shaded by a path composed entirely of triangles. The colour at each vertex of the triangle is specified, and a technique known as Gouraud interpolation is used to colour the interiors. The function dictionary is the optional entry of these types of shading dictionaries. When shading the device pixels, it is necessary to transform the device pixels to the shading coordinates and identify the location within the defined triangles in the shading space to determine the colours of the pixels to be painted.
Patch meshes based (Types 6 and 7) shading as described by the Postscript Language reference manual, defines the area to be shaded by a path composed entirely of patches bounded by four cubic Bezier curves. The colour at four intersection points of the boundary Bezier curves is specified, and two linear parameters (u,v) spanning 0.0 to 1.0 inclusive are used to interpolate the colour of interior of the patch. The interpolation is defined in the shading domain rather than in the device domain. The function dictionary is optional for these types of shading operation. When shading the device pixels, it needs to transform the device pixels to the shading coordinates and identify the location within the defined patches in the shading space to perform the corresponding colour interpolation.
In the above shading types, the necessity to transform the device coordinates to shading coordinates, simply to determine the colour at the device pixel is computationally expensive. Coordinate transformations also incur round-off errors when used with fixed-point arithmetic. In order to avoid such drawbacks, the colour computations should be performed in the device space.